#ifndef HEAPCOMM_H_INCLUDED
#define HEAPCOMM_H_INCLUDED

typedef int elem;
/**
*   important: array index start with 1
*/
void max_heapify(elem arr[],int index,int heapsize){
    int largest = index;
    int l = index*2;
    int r = l+1;
    if(l<=heapsize&&arr[l]>arr[index]){
        largest = l;
    }
    if(r<=heapsize&&arr[r]>arr[largest]){
        largest = r;
    }
    if(largest!=index){
        arr[0] = arr[index];
        arr[index]=arr[largest];
        arr[largest] = arr[0];
        max_heapify(arr,largest,heapsize);
    }
}

void build_max_heap(elem arr[],int heapsize){
    int offset = heapsize/2;
    while(offset>0){
        max_heapify(arr,offset,heapsize);
        offset--;
    }
}

void heap_sort(elem arr[],int heapsize){
    build_max_heap(arr,heapsize);
    while(heapsize>1){
        arr[0] = arr[1];
        arr[1] = arr[heapsize];
        arr[heapsize] = arr[0];
        heapsize--;
        max_heapify(arr,1,heapsize);
    }

}

void print_arr(elem arr[],int len){
    int i = 0;
    printf("arr [");
    for(i=1;i<=len;i++){
        printf("%d",arr[i]);
        if(i<len){
            printf(",");
        }
    }
    printf("] \n");
}
#endif // HEAPCOMM_H_INCLUDED
